백준 1504번
오늘 풀어본 문제는 백준의 1504번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
방향성이 없는 그래프가 주어진다. 세준이는 $1$ 번 정점에서 $N$ 번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. $1$ 번 정점에서 $N$ 번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 $N$ 과 간선의 개수 $E$ 가 주어진다. $(2 \le N \le 800, 0 \le E \le 200,000)$ 둘째 줄부터 $E$ 개의 줄에 걸쳐서 세 개의 정수 $a, b, c$ 가 주어지는데, $a$ 번 정점에서 $b$ 번 정점까지 양방향 길이 존재하며, 그 거리가 $c$ 라는 뜻이다. $(1 \le c \le 1,000)$ 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 $v_1$ 과 $v_2$ 가 주어진다. $(v_1 \ne v_2, v_1 \ne N, v_2 \ne 1)$ 임의의 두 정점 $u$ 와 $v$ 사이에는 간선이 최대 $1$ 개 존재한다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 $-1$ 을 출력한다.
풀이과정
1번째 시도
문제를 처음 보고, 다익스트라가 맞는 것 같기는 한데, 두 정점을 반드시 거쳐야 한다는 부분이 조금 신경 쓰였다. 내가 생각해낸 방법은 반드시 거쳐야하는 그 두 정점도 시작점으로 하여 총 $3$ 번 다익스트라 알고리즘을 돌린 뒤, 거리 $3$ 개의 길이를 더해 결과를 출력하는 방식으로 해결을 시도해보았다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
struct cmp {
bool operator()(const pair<int, int> a, const pair<int, int> b) {
return a.second > b.second;
}
};
vector<unordered_map<int, int>> graph(801);
int shortest[3][801] = {0,};
int visit[801] = {0,};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, E;
int starts[3] = {1, 0, 0};
cin >> N >> E;
for (int i=0; i<E; i++) {
int start, end, weight;
cin >> start >> end >> weight;
graph[start][end] = graph[end][start] = weight;
}
cin >> starts[1] >> starts[2];
for (int s=0; s<3; s++) {
for (int i=1; i<=N; i++) {
shortest[s][i] = INT_MAX;
visit[i] = false;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
pq.emplace(starts[s], 0);
while (!pq.empty()) {
pair<int, int> curr = pq.top();
pq.pop();
if (visit[curr.first] == false) {
visit[curr.first] = true;
for (auto& next : graph[curr.first]) {
if (curr.second + next.second < shortest[s][next.first]) {
shortest[s][next.first] = curr.second + next.second;
pq.emplace(next.first, shortest[s][next.first]);
}
}
}
}
}
cout << shortest[0][starts[1]] + shortest[1][starts[2]] + shortest[2][N];
return 0;
}
실행 결과 ‘컴파일 에러’가 발생하였다.
2번째 시도
컴파일 에러가 난 원인은 visit 변수가 모호하다는 것이었다. 추측컨대, 헤더 파일이나 어딘가에 같은 이름의 변수가 존재 했던 것 같다. 이름을 visited 로 바꿔준 뒤 다시 제출하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
struct cmp {
bool operator()(const pair<int, int> a, const pair<int, int> b) {
return a.second > b.second;
}
};
vector<unordered_map<int, int>> graph(801);
int shortest[3][801] = {0,};
int visited[801] = {0,};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, E;
int starts[3] = {1, 0, 0};
cin >> N >> E;
for (int i=0; i<E; i++) {
int start, end, weight;
cin >> start >> end >> weight;
graph[start][end] = graph[end][start] = weight;
}
cin >> starts[1] >> starts[2];
for (int s=0; s<3; s++) {
for (int i=1; i<=N; i++) {
shortest[s][i] = INT_MAX;
visited[i] = false;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
pq.emplace(starts[s], 0);
while (!pq.empty()) {
pair<int, int> curr = pq.top();
pq.pop();
if (visited[curr.first] == false) {
visited[curr.first] = true;
for (auto& next : graph[curr.first]) {
if (curr.second + next.second < shortest[s][next.first]) {
shortest[s][next.first] = curr.second + next.second;
pq.emplace(next.first, shortest[s][next.first]);
}
}
}
}
}
cout << shortest[0][starts[1]] + shortest[1][starts[2]] + shortest[2][N];
return 0;
}
실행 결과 ‘틀렸습니다’가 떴다.
3번째 시도
틀린 원인은 금방 알아낼 수 있었는데, 최단 경로가 존재하지 않을 경우에 $-1$ 을 출력해야 한다는 사실을 완전히 잊어버리고 있었다. 거리 $3$ 개 중 하나라도 길이가 INT_MAX, 즉 그런 경로가 존재하지 않는다면 $-1$ 을 출력하도록 코드를 수정하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
struct cmp {
bool operator()(const pair<int, int> a, const pair<int, int> b) {
return a.second > b.second;
}
};
vector<unordered_map<int, int>> graph(801);
int shortest[3][801] = {0,};
int visited[801] = {0,};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, E;
int starts[3] = {1, 0, 0};
cin >> N >> E;
for (int i=0; i<E; i++) {
int start, end, weight;
cin >> start >> end >> weight;
graph[start][end] = graph[end][start] = weight;
}
cin >> starts[1] >> starts[2];
for (int s=0; s<3; s++) {
for (int i=1; i<=N; i++) {
shortest[s][i] = INT_MAX;
visited[i] = false;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
pq.emplace(starts[s], 0);
while (!pq.empty()) {
pair<int, int> curr = pq.top();
pq.pop();
if (visited[curr.first] == false) {
visited[curr.first] = true;
for (auto& next : graph[curr.first]) {
if (curr.second + next.second < shortest[s][next.first]) {
shortest[s][next.first] = curr.second + next.second;
pq.emplace(next.first, shortest[s][next.first]);
}
}
}
}
}
if (shortest[0][starts[1]] == INT_MAX || shortest[1][starts[2]] == INT_MAX || shortest[2][N] == INT_MAX) {
cout << -1;
}
else {
cout << shortest[0][starts[1]] + shortest[1][starts[2]] + shortest[2][N];
}
return 0;
}
실행 결과 ‘틀렸습니다’가 떴다.
4번째 시도
여진히 틀린 이유가 무엇이었는지 찾아본 결과, 반드시 거쳐야 하는 정점으로 $1$ 이나 $N$ 번 정점이 올 수도 있었고, $v_1$ 과 $v_2$ 를 거치는 순서는 상관이 없다는 걸 눈치채지 못했기 때문이었다.
이를 해결하기 위해, 자기 자신으로 이동하는 최단 거리를 $0$ 으로 설정해준 뒤, $v_1$ 과 $v_2$ 가 바뀐 경로에 대해서도 검사하도록 코드를 수정해주었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
struct cmp {
bool operator()(const pair<int, int> a, const pair<int, int> b) {
return a.second > b.second;
}
};
vector<unordered_map<int, int>> graph(801);
int shortest[3][801] = {0,};
int visited[801] = {0,};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, E;
int starts[3] = {1, 0, 0};
cin >> N >> E;
for (int i=0; i<E; i++) {
int start, end, weight;
cin >> start >> end >> weight;
graph[start][end] = graph[end][start] = weight;
}
cin >> starts[1] >> starts[2];
for (int s=0; s<3; s++) {
for (int i=1; i<=N; i++) {
shortest[s][i] = INT_MAX;
if (i == starts[s]) {
shortest[s][i] = 0;
}
visited[i] = false;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
pq.emplace(starts[s], 0);
while (!pq.empty()) {
pair<int, int> curr = pq.top();
pq.pop();
if (visited[curr.first] == false) {
visited[curr.first] = true;
for (auto& next : graph[curr.first]) {
if (curr.second + next.second < shortest[s][next.first]) {
shortest[s][next.first] = curr.second + next.second;
pq.emplace(next.first, shortest[s][next.first]);
}
}
}
}
}
if ((shortest[0][starts[1]] == INT_MAX || shortest[1][starts[2]] == INT_MAX || shortest[2][N] == INT_MAX)
&& (shortest[0][starts[2]] == INT_MAX || shortest[2][starts[1]] == INT_MAX || shortest[1][N] == INT_MAX)) {
cout << -1;
}
else {
cout << min(shortest[0][starts[1]] + shortest[1][starts[2]] + shortest[2][N],
shortest[0][starts[2]] + shortest[2][starts[1]] + shortest[1][N]);
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
오늘 풀어본 문제는 엄청 어려운 문제까지는 아니었는데, 방심을 해버려 4번이나 제출을 하게 되었다. 좀 더 문제를 꼼꼼히 읽는 습관을 들이는 것이 좋을 것 같다.
이제 CLASS 4 MASTER 까지 단 한 문제 만이 남아있다. 신년이 오면 나는 이제 CLASS 5 로 나아갈 수 있게 될 것이다. 무척 기대된다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1504